//Bptree.cpp

#include"Bptree.h"
#include<iostream>

#ifndef _BPTREE_CPP_
#define _BPTREE_CPP_

Bpt::BPTree::BPTree()
{
    root = new BTNode();
    root->isLeaf = true;
    root->keyNum = 0;
    DiskWrite(root);
}


Bpt::BPTree::~BPTree()
{
    struct BTNode* pNode;
    std::queue<struct BTNode*> q;
    q.push(root);
    while (!q.empty()){
        pNode = q.front();
        q.pop();
        //bfs的方式进行delete
        if (pNode->isLeaf)
            continue;//这里是不是应该在continue之前先delete？
        for (int i = 0; i <= pNode->keyNum; i++)
            q.push(pNode->child[i]);
        delete pNode;
    }
}


void Bpt::BPTree::DiskWrite(BTNode* pNode)
{

}


void Bpt::BPTree::DiskRead(BTNode *pNode)
{

}


Bpt::BTNode* Bpt::BPTree::Search(BTNode* pNode, int key, int &index)
{
    int i = 0;
    while (i<pNode->keyNum&&key>pNode->key[i])i++;
    if (i < pNode->keyNum&&key == pNode->key[i]){//如果找到关键字，返回
        index = i;
        return pNode;
    }
    if (pNode->isLeaf)
        return NULL;
    else{
        DiskRead(pNode->child[i]);
        return Search(pNode->child[i], key, index);
    }
}


void Bpt::BPTree::InsertNonFull(BTNode* pNode, int key)
{
    int i = pNode->keyNum - 1;
    if (pNode->isLeaf){//如果是叶子结点，直接插入
        while (i >= 0 && key < pNode->key[i]){
            pNode->key[i + 1] = pNode->key[i];
            i--;
        }
        pNode->key[i + 1] = key;
        pNode->keyNum++;
        DiskWrite(pNode);
    }
    else {
        while (i >= 0 && key < pNode->key[i])i--;
        i++;
        DiskRead(pNode->child[i]);
        if (pNode->child[i]->keyNum == 2 * M - 1){
            SplitChild(pNode, i, pNode->child[i]);
            if (key>pNode->key[i]) i++;
        }
        InsertNonFull(pNode->child[i], key);
    }
}


void Bpt::BPTree::SplitChild(BTNode* parent, int i, BTNode* child)
{//调用该函数时，child内的关键字个数达到了2*M-1个，需要分解成(M-1) + (M-1) + 1
    int j;
    struct BTNode* pNode = new BTNode();
    pNode->isLeaf = child->isLeaf;
    pNode->keyNum = M - 1;
    for (j = 0; j < M - 1; j++)//将child结点的 后M-1个 关键字赋给新节点
        pNode->key[j] = child->key[j + M];
    if (!child->isLeaf){//如果child不是叶子结点，将其后M个孩子结点赋给新节点。
        for (j = 0; j < M; j++)
            pNode->child[j] = child->child[j + M];
    }
    child->keyNum = M - 1;

    for (j = parent->keyNum; j > i; j--)
        parent->child[j + 1] = parent->child[j];//将child结点的父节点parent下标i以后的结点指针都向后移动一位，
    parent->child[j + 1] = pNode;//将新生成的结点当成parent的一个孩子
    for (j = parent->keyNum - 1; j >= i; j--)    //将i后面的关键字都向后移动一位
        parent->key[j + 1] = parent->key[j];
    parent->key[j + 1] = child->key[M - 1];//将孩子结点的中间结点移到父节点的指定位置
    parent->keyNum++;
    DiskWrite(parent);
    DiskWrite(pNode);
    DiskWrite(child);
}


void Bpt::BPTree::merge(BTNode* parent, BTNode* pNode1, BTNode* pNode2, int index)
{
    //合并关键字
    pNode1->key[M - 1] = parent->key[index];
    for (int i = 0; i < M - 1; i++)//将pNode2的关键字移到pNode1中
        pNode1->key[i + M] = pNode2->key[i];
    pNode1->keyNum = 2 * M - 1;
    //合并非叶子节点的child指针
    if (!pNode1->isLeaf){//如果不是叶子，将pNode2的孩子指针也移到pNode1中
        for (int i = 0; i < M; i++)
            pNode1->child[i + M] = pNode2->child[i];
    }
    //整理parent节点上的数据
    //将父节点index以后的关键字以及孩子指针都向前移动一位
    for (int i = index; i < parent->keyNum; i++){
        parent->key[i] = parent->key[i + 1];
        parent->child[i + 1] = parent->child[i + 2];
    }
    parent->keyNum--;
    delete pNode2;
}

//所谓前继节点，就是key[i]左侧指针child[i]所指向的B+树中的最大关键字
int Bpt::BPTree::predecessor(BTNode* pNode)
{//在pNode节点指向的树中找到一个最大关键字
    while (!pNode->isLeaf)
        pNode = pNode->child[pNode->keyNum];
    return pNode->key[pNode->keyNum - 1];
}

//所谓后继节点，就是key[i]右侧指针child[i+1]所指向的B+树中的最小关键字
int Bpt::BPTree::successor(BTNode* pNode)
{
    while (!pNode->isLeaf)
        pNode = pNode->child[0];
    return pNode->key[0];
}


void Bpt::BPTree::ExchangeLeftNode(BTNode *parent, BTNode* pNode0, BTNode* pNode1, int index)
{
    for (int i = pNode1->keyNum; i > 0; i--)
        pNode1->key[i] = pNode1->key[i - 1];//pNode1结点所有关键字向后移动一位
    pNode1->key[0] = parent->key[index];//第0个关键字来自父节点
    pNode1->keyNum++;
    parent->key[index] = pNode0->key[pNode0->keyNum - 1];//父节点的index处的关键字来自pNode0的最大关键字

    if (!pNode0->isLeaf){//如果不是叶子结点，
        for (int i = pNode1->keyNum; i > 0; i--)//将pNode1的孩子指针都向后移动一位，并将pNode0的最后一个孩子指针赋给它的第一个
            pNode1->child[i] = pNode1->child[i - 1];
        pNode1->child[0] = pNode0->child[pNode0->keyNum];
    }

    pNode0->keyNum--;
}


void Bpt::BPTree::ExchangeRightNode(BTNode* parent, BTNode* pNode1, BTNode *pNode2, int index)
{
    pNode1->key[pNode1->keyNum] = parent->key[index];
    pNode1->keyNum++;
    parent->key[index] = pNode2->key[0];
    for (int i = 0; i < pNode2->keyNum - 1; i++)
        pNode2->key[i] = pNode2->key[i + 1];

    if (!pNode2->isLeaf){
        pNode1->child[pNode1->keyNum] = pNode2->child[0];
        for (int i = 0; i < pNode2->keyNum; i++)
            pNode2->child[i] = pNode2->child[i + 1];
    }
    pNode2->keyNum--;
}


/*删除算法的思路-伪代码
RemoveNonLess(BTNode* pNode, int key):从 以pNode指向的节点为根的子树 中删除关键字key
如果 [pNode 指向叶子节点]:
    如果 [key 在 pNode 中]:
        直接删除key即可
    否则:
        没有找到 key
否则:
    如果 [key 在 pNode 中]:
        如果 [key左侧子节点中关键字个数>=M]:
            获取key的前继关键字pre
            用pre 替代 pNode中的key(赋值操作，覆盖即删除)
            递归删除左子树中的pre: RemoveNonLess(key左侧子节点指针,pre)
        否则如果 [key右侧子节点中关键字个数>=M]:
            获取key的后继关键字suc
            用suc 替代 pNode中的key(赋值操作，覆盖即删除)
            递归删除右子树中的suc: RemoveNonLess(key右侧子节点指针,suc)
        否则:
            合并 左子节点关键字,key,右子节点关键字 到 左子节点 中
            递归删除左子节点中的key: RemoveNonLess(key右侧子节点指针,key)
    否则:
        pNode1 = pNode->child[i];//获取key的左邻指针
        如果 [存在pNode1的左邻指针]: 将其设为pNode0
        如果 [存在pNode1的右邻指针]: 将其设为pNode2
        //如果都存在则逻辑结构为: pNode0 -- key[i-1] -- pNode1 -- key[i] -- pNode2
        //三个不同的指针代表pNode的三个相邻的不同子结点,且 key[i-1] <= key <= key[i]
        //下面通过判断pNode012的关键字个数，使pNode02支援pNode1
        如果 [pNode1的关键字个数 == M-1]:
            如果 [pNode0存在 && pNode0的关键字个数>=M]:
                将key[i-1]借入pNode1节点内
                将key[i-1]向pNode0借一个最大关键字
                根据pNode0是否为叶子节点调整结构
            否则如果 [pNode2存在 && pNode2的关键字个数>=M]:
                将key[i]借入pNode2节点内
                将key[i]向pNode1借一个最小关键字
                根据pNode2是否为叶子节点调整结构
            否则如果 [pNode0存在]:
                合并pNode0到pNode1
            否则:
                合并pNode2到pNode1
        进入pNode1子树中删除key: RemoveNonLess(pNode1,key)
*/

void Bpt::BPTree::RemoveNonLess(BTNode* pNode, int key)
{
    if (pNode->isLeaf){//到了叶子结点，直接删除
        int i = 0;
        while (i<pNode->keyNum&&key>pNode->key[i])
            i++;
        if (i < pNode->keyNum&&key == pNode->key[i]){
            while (i < pNode->keyNum - 1){
                pNode->key[i] = pNode->key[i + 1];
                i++;
            }
            pNode->keyNum--;
        }
        else {
            std::cout << "not found!" << std::endl;
        }
    }
    else {
        int i = 0;
        while (i < pNode->keyNum&&key > pNode->key[i])//找到第一个大于等于key的关键字
            i++;
        if (i < pNode->keyNum&&key == pNode->key[i]){//在结点中找到要删除的关键字
            struct BTNode* pNode1 = pNode->child[i];//key[i]左侧指针
            struct BTNode* pNode2 = pNode->child[i + 1];//key[i]右侧指针
            if (pNode1->keyNum >= M){//如果关键字左边的孩子结点的关键字数大于等于M
                int target = predecessor(pNode1);//将其前继结点移到pNode中
                pNode->key[i] = target;
                RemoveNonLess(pNode1, target);//递归删除target
            }
            else if (pNode2->keyNum >= M){//右边，同理
                int target = successor(pNode2);
                pNode->key[i] = target;
                RemoveNonLess(pNode2, target);
            }
            else {
                merge(pNode, pNode1, pNode2, i);//都小于M，合并(删除pNode2保留pNode1)
                RemoveNonLess(pNode1, key);
            }
        }
        else {//不在此结点中，则目标可能在pNode1中
            struct BTNode *pNode1 = pNode->child[i];
            struct BTNode *pNode0 = NULL;
            struct BTNode *pNode2 = NULL;
            if (i>0)
                pNode0 = pNode->child[i - 1];//pNode1的左邻指针
            if (i < pNode->keyNum)
                pNode2 = pNode->child[i + 1];//pNode1的右邻指针
            if (pNode1->keyNum == M - 1){//如果要删除的孩子结点关键字个数为M-1
                if (i > 0 && pNode0->keyNum >= M){//如果左邻指针的结点至少有M个关键字，向其借一个
                    //pNode1向parent要一个结点key[index]，parent向pNode0要一个结点，pNode1关键字个数为M-1
                    ExchangeLeftNode(pNode, pNode0, pNode1, i - 1);
                }
                else if (i < pNode->keyNum&&pNode2->keyNum >= M){//同理，
                    ExchangeRightNode(pNode, pNode1, pNode2, i);
                }
                else if (i>0){//相邻结点都只有M-1个关键字且左邻结点存在，则合并pNode1及其左邻子结点
                    merge(pNode, pNode0, pNode1, i - 1);
                    pNode1 = pNode0;
                }
                else{//相邻结点都只有M-1个关键字 且左邻结点不存在 且右邻结点存在，则合并pNode1及其右邻结点
                    merge(pNode, pNode1, pNode2, i);
                }
                RemoveNonLess(pNode1, key);
            }
            else{
                RemoveNonLess(pNode1, key);
            }
        }
    }
}


Bpt::BTNode* Bpt::BPTree::search(int key, int &index)
{
    return Search(root, key, index);
}


void Bpt::BPTree::insert(int key)
{
    struct BTNode* r = root;
    if (root->keyNum == 2 * M - 1){//根节点特殊处理，如果根节点关键字个数为2*M-1，
        struct BTNode* pNode = new BTNode();//新建一个结点作为新的根节点，并将现在的根节点作为
        root = pNode;//新根节点的孩子结点
        pNode->isLeaf = false;
        pNode->keyNum = 0;
        pNode->child[0] = r;
        SplitChild(pNode, 0, r);//孩子结点r有2*M-1个关键字
        InsertNonFull(pNode, key);
    }
    else
        InsertNonFull(r, key);
}


void Bpt::BPTree::remove(int key)
{
    if (root->keyNum == 1){//如果根节点只有两个孩子
        struct BTNode* pNode1 = root->child[0];
        struct BTNode* pNode2 = root->child[1];
        if (pNode1->keyNum == M - 1 && pNode2->keyNum == M - 1){//且两个孩子都只有M-1个关键字，合并
            //没有删除操作
            merge(root, pNode1, pNode2, 0);
            delete root;
            root = pNode1;
        }
        else {
            RemoveNonLess(root, key);
        }
    }
    else {
        RemoveNonLess(root, key);
    }
}

void Bpt::BPTree::PrintRow()
{
    struct BTNode* pNode;
    std::queue<struct BTNode*> q;
    q.push(root);
    while (!q.empty()){
        pNode = q.front();
        q.pop();
        std::cout << "[ ";
        for (int i = 0; i < pNode->keyNum; i++)
            std::cout << pNode->key[i] << " ";
        std::cout << "]" << std::endl;
        if (pNode->isLeaf)
            continue;
        for (int i = 0; i <= pNode->keyNum; i++)
            q.push(pNode->child[i]);
    }
}

#endif //_BPTREE_CPP_
